package seqlist.leetcode;

/**
 * 以x为轴拆分链表
 * @author yuisama
 * @date 2022/04/24 19:44
 **/
public class Num02_04_PartitionList {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode smallHead = new ListNode();
        ListNode smallTail = smallHead;
        ListNode bigHead = new ListNode();
        ListNode bigTail = bigHead;
        // 扫描原链表
        while (head != null) {
            if (head.val < x) {
                smallTail.next = head;
                smallTail = head;
            }else {
                bigTail.next = head;
                bigTail = head;
            }
            head = head.next;
        }
        // 大链表的末尾断掉
        bigTail.next = null;
        // 拼接小链表与大链表
        smallTail.next = bigHead.next;
        return smallHead.next;
    }
}